package 题目集.拓扑排序;

import java.util.Arrays;
import java.util.Scanner;

public class ch05_最大员工数2 {
    /**https://leetcode.cn/problems/maximum-employees-to-be-invited-to-a-meeting/description/
     * 这题有两种情况：
     *     一种是选多个小环的情况、一种是选一个大环的情况。小环可以存在多个，大环只能存在一个（有大环就不能有其他环）。
     *      答案即是 所有小环的员工数以及他们的最长链之和 与 大环的员工数中较大的一个。
     * 通过拓扑排序筛选出环和他们链条的最大长度，再判断环是大环还是小环。
     */
    static int[] graph;
    static int[] inDeg;
    static int n;
    static int smallSize, moreSize; //大环和长度为2的环
    static int[] queue;
    static int[] size;  //每个节点的最长链
    static int h, t;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        graph = new int[n + 1];
        inDeg = new int[n + 1];
        queue = new int[n + 1];
        size = new int[n + 1];
        Arrays.fill(size, 1);
        for (int i = 1; i <= n; i++) {
            graph[i] = sc.nextInt();
            inDeg[graph[i]]++;
        }
        int res = topoSort();
        System.out.println(res);
    }

    public static int topoSort() {
        for (int i = 1; i <= n; i++) {
            if (inDeg[i] == 0) {
                queue[t++] = i;
            }
        }
        while (h < t) {
            int cur = queue[h++];
            int next = graph[cur];
            size[next] = Math.max(size[next], size[cur] + 1);
            inDeg[next]--;    //它邻接点入度--
            if (inDeg[next] == 0) {
                queue[t++] = next;
            }
        }
        for (int i = 1; i <= n; i++) {
            if (inDeg[i] != 0) {   //发现环
                int ringSize = 1;
                inDeg[i] = 0;
                for (int next = graph[i]; next != i; next = graph[next]) {
                    ringSize++;
                    inDeg[next] = 0;
                }
                if (ringSize > 2) {
                    moreSize = Math.max(moreSize, ringSize);
                } else {
                    smallSize += size[i] + size[graph[i]];
                }
            }
        }
        return Math.max(smallSize,moreSize);
    }
}
